package parser;
import java.util.LinkedList;
import java.util.List;

import exprtree.AddExpr;
import exprtree.CosExpr;
import exprtree.DivExpr;
import exprtree.DoubleLitExpr;
import exprtree.Expr;
import exprtree.MinusExpr;
import exprtree.MultExpr;
import exprtree.PowExpr;
import exprtree.SinExpr;
import exprtree.SqrtExpr;
import exprtree.TanExpr;
import exprtree.UnaryMinusExpr;
import exprtree.VarExpr;

/** 
 * @author Brad
 */
public class Parser {

	private String input;
	private List<Token> symbols;  //Tokenized String
	private LinkedList<Token> postFixed;  //Tokenized String
	private LinkedList<Expr> exprStack = new LinkedList<Expr>();

	public Expr parse(String expressionToParse) throws LexError, ParseError{
		input = expressionToParse;
		
		//Try to symbolize the Expr with the Lexer
		Lexer lex = new Lexer();
		symbols = lex.lex(input);
		
		postFixed = toPostFix();
		
		//Now Parse the Tokens
		return parse();		
	}
	
	public Expr parse() throws ParseError{
		while(postFixed.size() > 0){
			if(postFixed.peekFirst().lexSymbol == LexSymbol.NUMBER){
				double value = Double.parseDouble(postFixed.pollFirst().matchedString);
				DoubleLitExpr constExpr = new DoubleLitExpr(value);
				exprStack.addLast(constExpr);
			} else if(postFixed.peekFirst().lexSymbol == LexSymbol.VAR){
				VarExpr var = new VarExpr();
				postFixed.pollFirst();
				exprStack.add(var);
			} else if(isBinaryOp(postFixed.peekFirst().lexSymbol)){
				Token op = postFixed.pollFirst();
				
				//Pop last two expressions and push the addExpr back on.
				Expr rightExpr = exprStack.pollLast();
				Expr leftExpr = exprStack.pollLast();
				
				switch (op.lexSymbol){
				case ADD:
					exprStack.addLast(new AddExpr(leftExpr, rightExpr)); break;
				case SUBTRACT:
					exprStack.addLast(new MinusExpr(leftExpr, rightExpr)); break;
				case MULTIPLY: 
					exprStack.addLast(new MultExpr(leftExpr, rightExpr)); break; 
				case DIVIDE: 
					exprStack.addLast(new DivExpr(leftExpr, rightExpr)); break;
				case CARROT:
				case POW:
					exprStack.addLast(new PowExpr(leftExpr, rightExpr)); break;
				default: break;
				}
			} else if(isUnaryOp(postFixed.peekFirst().lexSymbol)){
				Token op = postFixed.pollFirst();
				
				//Pop last two expressions and push the addExpr back on.
				Expr expr = exprStack.pollLast();
				
				switch (op.lexSymbol){
				case SIN:
					exprStack.addLast(new SinExpr(expr)); break;
				case COS:
					exprStack.addLast(new CosExpr(expr)); break;
				case TAN:
					exprStack.addLast(new TanExpr(expr)); break;
				case UNARYMINUS:
					exprStack.addLast(new UnaryMinusExpr(expr)); break;
				case SQRT:
					exprStack.addLast(new SqrtExpr(expr)); break;
				default: break;
				}
			}
		}
		if(exprStack.size() == 1){
			return exprStack.poll();
		}
		else{
			//Some parsing error.
			String error = "Error:  Tokens left on expr stack";
			while(exprStack.size() >= 1){
				error  = error + "\n" + exprStack.poll().getClass().getName();
			}
			
			throw new ParseError(error);
			
		}
	}
	
	//Returns the post fix form of the symbols.
	//Shunting Yard algorithm for converting infix to postfix...
	private LinkedList<Token> toPostFix(){
		LinkedList<Token> operands = new LinkedList<Token>();
		LinkedList<Token> operators = new LinkedList<Token>();
		for(int i = 0; i < symbols.size(); i++){
			Token t = symbols.get(i);
			if(t.lexSymbol == LexSymbol.NUMBER || t.lexSymbol == LexSymbol.VAR){
				operands.addLast(t);
			} else if(isOp(t.lexSymbol)){
				//If Left Associative and Precedence is less than or equal to last operator     OR
				//If Right Associative and Precedence is less than last operator
				while((operators.size() > 0) &&
						((t.isLeftAssociative && t.precedence <= operators.getLast().precedence) ||
						(!t.isLeftAssociative && t.precedence < operators.getLast().precedence))){
					 operands.addLast(operators.pollLast());
				}
				operators.addLast(t);
			}
			
			else if(t.lexSymbol == LexSymbol.LEFT_PAREN){
				operators.addLast(t);
			}
			
			else if(t.lexSymbol == LexSymbol.RIGHT_PAREN){
				while(operators.size() > 0 && operators.getLast().lexSymbol != LexSymbol.LEFT_PAREN){
					operands.addLast(operators.pollLast());
				}
				if(operators.size() > 0){
					if(operators.getLast().lexSymbol == LexSymbol.LEFT_PAREN){
						operators.pollLast();   // Pop Left_ Paren
					}
				}
				else{
					System.err.println("Fail!!!");
					//Mismatched Parentheses.
				}
			}
			//printStacks(operands, operators);
		}
		while(operators.size() > 0){
			operands.addLast(operators.pollLast());
			//printStacks(operands, operators);
		}
		return operands;
	}

	private boolean isOp(LexSymbol symbol){
		return (isBinaryOp(symbol) || isUnaryOp(symbol));
	}
	
	private boolean isBinaryOp(LexSymbol symbol){
		switch (symbol){
		case ADD:
		case SUBTRACT:
		case MULTIPLY:
		case DIVIDE:
		case CARROT:
		case POW:
			return true;
		}
		return false;
	}
	
	private boolean isUnaryOp(LexSymbol symbol){
		switch(symbol){
		case SIN:
		case COS:
		case TAN:
		case SQRT:
		case UNARYMINUS:
			return true;
		}
		return false;
	}
}